#coding: utf-8

from typing import List


class Solution:
    def getListSum(self,nums:List[int]) -> List[int]:
        sum = 0
        for num in nums:
            sum = sum + num
        return sum

    def isInAns(self,tmp,ans):
        # 查找tmp 是否在 ans 中
        for nums in ans:
            if nums[0] == tmp[0] and nums[1] == tmp[1] and \
                nums[2] == tmp[2] and nums[3] == tmp[3]:
                return True
        return False

    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:         
        length = len(nums)
        nums.sort()
        ans = []
        for i in range(length):
            for j in range(i+1,length):
                low = j+1
                high = length-1
                while low < high:
                    tmp = [nums[i],nums[j],nums[low],nums[high]]
                    sum = self.getListSum(tmp)

                    if sum == target:
                        if not self.isInAns(tmp,ans):
                            ans.append(tmp)
                        low = low + 1
                    elif sum < target:
                        low = low + 1
                    else:
                        high = high - 1
        
        return ans

if __name__ == '__main__':
    solu = Solution()
    print(solu.fourSum([1,0,-1,0,-2,2],0))
